class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0,candy = -1;
        for(int i = 0;i < nums.size();i++){
            if(cnt == 0){
                cnt = 1;
                candy = nums[i];
            }else{
                if(candy != nums[i]) {
                    cnt--;
                }
                else cnt++;
            }
        }
        return candy;
    }
};